package leetcode.code1092;

import leetcode.IDebug;
import leetcode.helper.H;
//超出内存限制
public class Solution2 implements IDebug {
	

	public String shortestCommonSupersequence(String str1, String str2) {
		int m = str1.length(), n = str2.length();
		String[][] dp = new String[m + 1][n + 1];
		dp[0][0] = "";
		for (int i = 1; i <= n; i++) {
			dp[0][i] = str2.substring(0, i);
		}
		for (int i = 1; i <= m; i++) {
			dp[i][0] = str1.substring(0, i);
		}
		for (int i = 1; i <= m; i++) {
			char c1 = str1.charAt(i - 1);
			for (int j = 1; j <= n; j++) {
				char c2 = str2.charAt(j - 1);
				if (c1 == c2) {
					dp[i][j] = dp[i - 1][j - 1] + c1;
				}
				String tmp1 = dp[i][j - 1] + c2;
				if (dp[i][j] == null) {
					dp[i][j] = tmp1;
				} else if (tmp1.length() < dp[i][j].length()) {
					dp[i][j] = tmp1;
				}
				String tmp2 = dp[i - 1][j] + c1;
				if (tmp2.length() < dp[i][j].length()) {
					dp[i][j] = tmp2;
				}
			}
		}
		return dp[m][n];
	}


	@Override
	public void debug4() {
		H.compare("cabac", this.shortestCommonSupersequence("abac", "cab"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
